#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int cache[90][90][90];

bool matchHelper(string s1, string s2, string s3)
{
    if (s1.size() == 0) return s2 == s3;
    if (s2.size() == 0) return s1 == s3;
    if (cache[s1.size()][s2.size()][s3.size()] != -1) return cache[s1.size()][s2.size()][s3.size()];
    bool ans = false;
    if (s1[0] == s3[0]) {
        ans = matchHelper(s1.substr(1), s2, s3.substr(1));
    }

    if (s2[0] == s3[0] && ans == false)
        ans = matchHelper(s1, s2.substr(1), s3.substr(1));
    cache[s1.size()][s2.size()][s3.size()] = ans;
    return ans;
}


//this could not pass 1337's larger test case
bool isInterleave2(string s1, string s2, string s3) {
    for (int i = 0; i < 90; i++) 
        for (int j = 0; j < 90; j++)
            for (int k = 0; k < 90; k++)
                cache[i][j][k] = -1;

     if (s1.size() + s2.size() != s3.size()) return false;
     if (matchHelper(s1.c_str(), s2.c_str(), s3.c_str())) return true;
     else return false; 
}

bool isInterleave(string s1, string s2, string s3) {
    if (s1.size() + s2.size() != s3.size()) return false;
    
    vector<vector<bool> > dp(s1.size()+1, vector<bool>(s2.size()+1, false));

    dp[0][0] = true; 
    
    for (int i = 1; i <= s1.size(); i++) {
        if (s1.substr(0,i) == s3.substr(0,i)) dp[i][0] = true;
        else break;
    }   

    for (int j = 1; j <= s2.size(); j++) {
        if (s2.substr(0,j) == s3.substr(0,j)) dp[0][j] = true;
        else break;
    }

    for (int i = 1; i <= s1.size(); i++) 
        for (int j = 1; j <= s2.size(); j++) 
            dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1])
                   || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
    return dp[s1.size()][s2.size()];
}


int main(int argc, char **argv)
{
    cout << isInterleave("a", "", "a");
    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;
}
